using System.Collections.Generic;
using Rb.Core.Maths;

namespace Poc0.LevelEditor.Core.Geometry
{
	/// <summary>
	/// Er... tesselates level geometry?
	/// </summary>
	internal class LevelGeometryTesselator
	{
		/// <summary>
		/// Tesselator edge type
		/// </summary>
		public class Edge
		{
			public Edge( int startIndex, int endIndex, Polygon neighbour )
			{
				m_StartIndex	= startIndex;
				m_EndIndex		= endIndex;
				m_Neighbour		= neighbour;
			}

			public int StartIndex
			{
				get { return m_StartIndex; }
				set { m_StartIndex = value; }
			}

			public int EndIndex
			{
				get { return m_EndIndex; }
				set { m_EndIndex = value; }
			}

			public Polygon Neighbour
			{
				get { return m_Neighbour; }
				set { m_Neighbour = value; }
			}

			private int m_StartIndex;
			private int m_EndIndex;
			private Polygon m_Neighbour;
		}

		/// <summary>
		/// Tesselator output polygon type
		/// </summary>
		public class Polygon
		{
			/// <summary>
			/// Default constructor
			/// </summary>
			public Polygon( )
			{
			}

			/// <summary>
			/// Setup constructor
			/// </summary>
			public Polygon( Edge[] edges )
			{
				m_Edges = edges;
			}

			/// <summary>
			/// Polygon edges
			/// </summary>
			public Edge[] Edges
			{
				get { return m_Edges; }
				set { m_Edges = value; }
			}

			/// <summary>
			/// Gets the level polygon associated with this polygon
			/// </summary>
			public LevelPolygon LevelPolygon
			{
				get { return m_LevelPoly; }
				set { m_LevelPoly = value; }
			}

			#region Private members

			private LevelPolygon m_LevelPoly;
			private Edge[] m_Edges;

			#endregion
		}

		/// <summary>
		/// Creates an initial bounding polygon
		/// </summary>
		public Polygon CreateBoundingPolygon( float minX, float minY, float maxX, float maxY )
		{
			int[] pointIndices = new int[]
				{
					AddPoint( new Point2( minX, minY ) ),
					AddPoint( new Point2( maxX, minY ) ),
					AddPoint( new Point2( maxX, maxY ) ),
					AddPoint( new Point2( minX, maxY ) )
				};

			return new Polygon
			(
				new Edge[]
					{
						new Edge( pointIndices[ 0 ], pointIndices[ 1 ], null ),
						new Edge( pointIndices[ 1 ], pointIndices[ 2 ], null ),
						new Edge( pointIndices[ 2 ], pointIndices[ 3 ], null ),
						new Edge( pointIndices[ 3 ], pointIndices[ 0 ], null ),
					}
			);
		}

		public delegate void AddPolygonDelegate( Polygon poly, Csg2.Node node );

		/// <summary>
		/// Builds the convex region for a node and its children
		/// </summary>
		public void BuildConvexRegions( Csg2.Node node, Polygon poly, AddPolygonDelegate addFloorPoly, AddPolygonDelegate addObstaclePoly, bool fixTJunctions )
		{
			Polygon behindPoly;
			Polygon inFrontPoly;
			Split( node.Plane, poly, out behindPoly, out inFrontPoly );

			if ( node.Behind != null )
			{
				BuildConvexRegions( node.Behind, behindPoly, addFloorPoly, addObstaclePoly, fixTJunctions );
			}
			else if ( addFloorPoly != null )
			{
				addFloorPoly( behindPoly, node );
			}
			if ( node.InFront != null )
			{
				BuildConvexRegions( node.InFront, inFrontPoly, addFloorPoly, addObstaclePoly, fixTJunctions );
			}
			else if ( addObstaclePoly != null )
			{
				addObstaclePoly( inFrontPoly, node );
			}
		}

		/// <summary>
		/// Gets the points generated by all splits so far
		/// </summary>
		public List<Point2> Points
		{
			get { return m_Points; }
		}

		/// <summary>
		/// Splits a source polygon along a plane, returning the sub-poly behind the plane in "behind"
		/// and the sub-poly in-front of the plane in "inFront"
		/// </summary>
		public void Split( Plane2 plane, Polygon source, out Polygon behind, out Polygon inFront )
		{
			float tolerance = 0.001f;
			int firstDefiniteClassIndex = -1;
			PlaneClassification[] classifications = new PlaneClassification[ source.Edges.Length ];
			bool edgeIsOnPlane = false;
			for ( int index = 0; index < source.Edges.Length; ++index )
			{
				classifications[ index ] = plane.ClassifyPoint( m_Points[ source.Edges[ index ].StartIndex ], tolerance );
				if ( ( firstDefiniteClassIndex == -1 ) && ( classifications[ index ] != PlaneClassification.On ) )
				{
					firstDefiniteClassIndex = index;
				}
			}
			int lastIndex = classifications.Length - 1;
			for ( int index = 0; index < classifications.Length; ++index )
			{
				if ( ( classifications[ lastIndex ] == PlaneClassification.On ) && ( classifications[ index ] == PlaneClassification.On ) )
				{
					edgeIsOnPlane = true;
					break;
				}
				lastIndex = index;
			}
			if ( edgeIsOnPlane )
			{
				//	One of the polygon's edges is on the plane. This means that we can easily classify the
				//	polygon as either behind or in front depending on the first definite class
				if ( classifications[ firstDefiniteClassIndex ] == PlaneClassification.Behind )
				{
					behind = new Polygon( source.Edges );
					inFront = null;
				}
				else
				{
					behind = null;
					inFront = new Polygon( source.Edges );
				}
				return;
			}

			List<Edge> behindEdges = new List<Edge>( source.Edges.Length + 1 );
			List<Edge> inFrontEdges = new List<Edge>( source.Edges.Length + 1 );

			int inFrontSplitEdgeIndex = -1;
			int behindSplitEdgeIndex = -1;

			behind = new Polygon( );
			inFront = new Polygon( );

			for ( int count = 0; count < source.Edges.Length; ++count )
			{
				int next = ( count + 1 ) % source.Edges.Length;
				Edge srcEdge = source.Edges[ count ];
				if ( classifications[ count ] == classifications[ next ] )
				{
					if ( classifications[ count ] == PlaneClassification.Behind )
					{
						behindEdges.Add( srcEdge );
					}
					else
					{
						inFrontEdges.Add( srcEdge );
					}
				}
				else if ( classifications[ count ] == PlaneClassification.On )
				{
					//	We know that the end index is not classified as "On", because this function early-outs
					//	if there's 2 or more points on the split plane
					if ( classifications[ next ] == PlaneClassification.Behind )
					{
						behindEdges.Add( srcEdge );
					}
					else
					{
						inFrontEdges.Add( srcEdge );
					}
				}
				else if ( classifications[ next ] == PlaneClassification.On )
				{
					if ( classifications[ count ] == PlaneClassification.Behind )
					{
						System.Diagnostics.Debug.Assert( inFrontSplitEdgeIndex == -1 );
						inFrontSplitEdgeIndex = inFrontEdges.Count;
						inFrontEdges.Add( null );
						behindEdges.Add( srcEdge );
					}
					else
					{
						System.Diagnostics.Debug.Assert( behindSplitEdgeIndex == -1 );
						behindSplitEdgeIndex = behindEdges.Count;
						behindEdges.Add( null );
						inFrontEdges.Add( srcEdge );
					}
					
				}
				else
				{
					//	Edge straddles split plane. Determine the intersection
					Point2 startPt = m_Points[ srcEdge.StartIndex ];
					Point2 endPt = m_Points[ srcEdge.EndIndex ];
					Line2Intersection intersection = Intersections2.GetLinePlaneIntersection( startPt, endPt, plane );
					int newPtIndex = AddPoint( intersection.IntersectionPosition );

					//	Find the edge in the neighbour polygon, and split that too
					if ( classifications[ count ] == PlaneClassification.Behind )
					{
						SplitNeighbourEdge( srcEdge, newPtIndex, behind, inFront );	
					}
					else
					{
						SplitNeighbourEdge( srcEdge, newPtIndex, inFront, behind );	
					}

					Edge startToMid = new Edge( srcEdge.StartIndex, newPtIndex, srcEdge.Neighbour );
					Edge midToEnd = new Edge( newPtIndex, srcEdge.EndIndex, srcEdge.Neighbour );

					if ( classifications[ count ] == PlaneClassification.Behind )
					{
						System.Diagnostics.Trace.Assert( inFrontSplitEdgeIndex == -1 );
						inFrontSplitEdgeIndex = inFrontEdges.Count;
						inFrontEdges.Add( null );

						behindEdges.Add( startToMid );
						inFrontEdges.Add( midToEnd );
					}
					else
					{
						System.Diagnostics.Trace.Assert( behindSplitEdgeIndex == -1 );
						behindSplitEdgeIndex = behindEdges.Count;
						behindEdges.Add( null );

						inFrontEdges.Add( startToMid );
						behindEdges.Add( midToEnd );
					}
				}
			}

			System.Diagnostics.Debug.Assert( behindEdges.Count > 0 );
			System.Diagnostics.Debug.Assert( inFrontEdges.Count > 0 );

			AddSplitEdge( behindEdges, behindSplitEdgeIndex, inFront );
			AddSplitEdge( inFrontEdges, inFrontSplitEdgeIndex, behind );

			behind.Edges = behindEdges.ToArray( );
			inFront.Edges = inFrontEdges.ToArray( );
		}

		private static void SplitNeighbourEdge( Edge srcEdge, int midPointIndex, Polygon startPoly, Polygon endPoly )
		{
			Polygon neighbour = srcEdge.Neighbour;

			if ( neighbour == null )
			{
				return;
			}

			Edge[] edges = neighbour.Edges;

			for ( int edgeIndex = 0; edgeIndex < edges.Length; ++edgeIndex )
			{
				Edge edge = edges[ edgeIndex ];
			//	if ( ( ( edge.StartIndex == srcEdge.StartIndex ) && ( edge.EndIndex == srcEdge.EndIndex ) ) ||
			//		 ( ( edge.EndIndex == srcEdge.StartIndex ) && ( edge.StartIndex == srcEdge.EndIndex ) ) )
				bool backwardMatch = ( edge.EndIndex == srcEdge.StartIndex ) && ( edge.StartIndex == srcEdge.EndIndex );
				bool forwardMatch = !backwardMatch && ( ( edge.StartIndex == srcEdge.StartIndex ) && ( edge.EndIndex == srcEdge.EndIndex ) );
				if ( backwardMatch || forwardMatch )
				{
					Edge[] newEdges = new Edge[ edges.Length + 1 ];
					int newIndex = 0;
					int oldIndex = 0;
					while ( oldIndex < edgeIndex )
					{
						newEdges[ newIndex++ ] = edges[ oldIndex++ ];
					}
					++oldIndex; //	Skip
					newEdges[ newIndex++ ] = new Edge( edge.StartIndex, midPointIndex, forwardMatch ? startPoly : endPoly );
					newEdges[ newIndex++ ] = new Edge( midPointIndex, edge.EndIndex, forwardMatch ? endPoly : startPoly );
					while ( oldIndex < edges.Length )
					{
						newEdges[ newIndex++ ] = edges[ oldIndex++ ];
					}

					neighbour.Edges = newEdges;
					return;
				}
			}
		}

		private static Edge AddSplitEdge( IList< Edge > edges, int splitEdgeIndex, Polygon neighbour )
		{
			Edge previousEdge = edges[ splitEdgeIndex == 0 ? edges.Count - 1 : splitEdgeIndex - 1 ];
			Edge nextEdge = edges[ ( splitEdgeIndex + 1 ) % edges.Count ];

			edges[ splitEdgeIndex ] = new Edge( previousEdge.EndIndex, nextEdge.StartIndex, neighbour );

			return edges[ splitEdgeIndex ];
		}

		#region Private members

		private readonly List< Point2 > m_Points = new List< Point2 >( );

		/// <summary>
		/// Adds a point to the point list and returns its index
		/// </summary>
		private int AddPoint( Point2 pt )
		{
			int index = m_Points.Count;
			m_Points.Add( pt );
			return index;
		}

		#endregion
	}
}
